package leetcode.code0828;

public class Solution3 extends Solution828 {

	private static final char A = 'A';
	private int M = (int) 1e9 + 7;

	@Override
	public int uniqueLetterString(String s) {
		int len = s.length();
		int ans = 0;
		char[] chars = s.toCharArray();
//		int[][] dp = new int[len][len];
		int[] dp = new int[len];
		for (int i = 0; i < len; i++) {
			dp[i] = 1;
			ans += 1;
		}
		for (int row = 1; row < len; row++) {
			int[] dic = new int[26];
			int l = len - row - 2;
			int r = len - 2;
			for (int i = r; i > l; i--) {
				dic[chars[i] - A]++;
			}
			for (int col = len - 1; col >= row; col--) {
				char c = chars[col];
				int num = 0;
				int cur = c - A;
				if (dic[cur] == 0) {
					num = dp[col - 1] + 1;
				} else if (dic[cur] == 1) {
					num = dp[col - 1] - 1;
				} else {
					num = dp[col - 1];
				}
				dp[col] = num;
				ans += num;
				ans = (ans + M) % M;
				if (l >= 0)
					dic[chars[l--] - A]++;
				dic[chars[r--] - A] -= 1;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
